/*2、编写一个算法，实现链式存储下的冒泡排序。(其实链表更适合插入排序)*/

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<string.h>
#include<Windows.h>

int NUM_SIZE = 20;
int MAX_MUN = 99999;
int SEED = 0;

struct NODE;
typedef struct NODE node;
struct NODE{int data;node* next;};

void print_linkedlist(const node* p){
    p=p->next;
    while(p){printf("%d ",p->data);p = p->next;}
    putchar('\n');
}

void show_linked_list_bubble_sort(node* p,int n){
    int i,j,cmp,mov,tmp;
    node* aj; // track a[j]
    cmp = mov = 0;
    SYSTEMTIME pt1,pt2;
    GetSystemTime(&pt1);
    for(i=0;i<n;i++){
        aj = p->next;
        for(j=0;j<n-i-1;++j){
            if( ++cmp && aj->data > aj->next->data ){ 
                tmp = aj->data; aj->data = aj->next->data; aj->next->data = tmp; ++mov;
            }
            aj = aj->next;
        }
    }
    GetSystemTime(&pt2);
    long long total = (pt2.wMilliseconds - pt1.wMilliseconds) + (pt2.wSecond - pt1.wSecond) * 1000;
    printf("----- Bubble Sort -----\nElement count: %d\nTotal time: %d ms\n",n,total);
    printf("Compare: %d\nMove: %d\n",cmp,mov);
    printf("Sort result(show first 20 elements):\n");
    if(n>20)n=20;
    for(i=0,aj=p->next;i<n;i++,aj=aj->next)printf("%d ",aj->data);putchar('\n');
}

int main(int argc,char** argv){
    int i,j,k,l;
    for(i=0;i<argc;i++){
        if( ( strcmp("-s",argv[i])==0 || strcmp("--size",argv[i])==0 ) )NUM_SIZE=atoi(argv[i+1]);
        if( ( strcmp("-m",argv[i])==0 || strcmp("--max",argv[i])==0 ) )MAX_MUN=atoi(argv[i+1]);
        if( ( strcmp("-d",argv[i])==0 || strcmp("--seed",argv[i])==0 ) )SEED=atoi(argv[i+1]);
    }
    if(SEED<0)SEED = time(NULL); srand(SEED);

    node head; head.data = NUM_SIZE; head.next = NULL;
    node* phead = &head;
    node* p = phead;
    for(i=0;i<NUM_SIZE;i++){p->next = malloc(sizeof(node));
    p=p->next;p->data=rand()%MAX_MUN;p->next=NULL;}

    show_linked_list_bubble_sort(phead,NUM_SIZE);

    phead = phead->next; // head is not malloc'ed
    while(phead){ p = phead;phead = phead->next;free(p);};
    return 0;
}
